import java.util.PriorityQueue;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: Administrator
 * \* Date: 2022/2/21
 * \* Time: 17:28
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class Heap {
    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        //默认是小根堆
        priorityQueue.offer(9);
        priorityQueue.offer(8);
        priorityQueue.offer(7);
        priorityQueue.offer(5);
        priorityQueue.offer(4);
        priorityQueue.offer(6);
        priorityQueue.offer(3);
        priorityQueue.offer(0);
        priorityQueue.offer(2);
        priorityQueue.offer(1);
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
    }
//向下调整
    public static void shiftDown(int[] array, int size, int index){
        int left = 2*index +1;
        while(left < size){
            int min = left;
            int right = 2*index +2;
            if(right<size){
                if(array[right] < array[left]){
                    min = right;
                }
            }
            if(array[index] <= array[min]){
                break;
            }
            int tmp = array[index];
            array[index] = array[min];
            array[min] = tmp;
            index = min;
            left = 2*index +1;
        }
    }



    //入队列
    public static void shiftUp(int[] array, int index){
        while(index > 0){
            int parent = (index -1) / 2;
            if(array[parent] >= array[index]){
                break;
            }
            int tmp =array[parent];
            array[parent] = array[index];
            array[index] = tmp;

            index = parent;
        }
    }

    //返回队首元素
    public class MyPriorityQueue{
        private int[] array = new int[100];
        private int size = 0;

        public void offer(int e){
            array[size++] = e;
            shiftUp(array , size - 1);
        }


        public boolean isFull(){
            return size == array.length;

        }
        public int poll(){
            if(isEmpty()){
                throw new RuntimeException("优先级队列为空");
            }
            int tmp =array[0];
            array[0] = array[size - 1];
            array[size - 1] = tmp;
            size--;
            shiftDown(array,size,0);
            return tmp;
        }

        public boolean isEmpty(){
            return size ==0;
        }
    }
}
